﻿#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;

class Solution
{
public:
    int lengthOfLIS(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> ret;
        ret.push_back(nums[0]);

        for (int i = 0; i < n; i++)
        {
            if (nums[i] >= ret.back())
            {
                ret.push_back(nums[i]);
            }
            else
            {
                int left = 0, right = ret.size() - 1;
                while (left < right)
                {
                    int mid = (left + right) >> 1;
                    if (ret[mid] < nums[i])
                        left = mid + 1;
                    else
                        right = mid;
                }
                ret[left] = nums[i];
            }
        }

        return ret.size();
    }
};

class Solution
{
public:
    bool increasingTriplet(vector<int>& nums)
    {
        int a = nums[0];
        int b = INT_MAX;

        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] > b)
                return true;
            else if (nums[i] > a)
                b = min(b, nums[i]);
            else
                a = min(a, nums[i]);
        }

        return false;
    }
};

class Solution
{
public:
    int findLengthOfLCIS(vector<int>& nums)
    {
        int ret = 0;
        int len = 1;

        for (int i = 1; i < nums.size(); i++)
        {
            if (nums[i] > nums[i - 1])
            {
                len++;
            }
            else
            {
                ret = max(ret, len);
                len = 1;
            }
        }

        return max(ret, len);
    }
};

class Solution
{
public:
    int maxProfit(vector<int>& prices)
    {
        int ret = 0;
        int minPrices = INT_MAX;

        for (int i = 0; i < prices.size(); i++)
        {
            ret = max(prices[i] - minPrices, ret);
            minPrices = min(minPrices, prices[i]);
        }

        return ret;
    }
};

class Solution
{
public:
    int maxProfit(vector<int>& prices)
    {
        int ret = 0, buy = 0;

        for (int i = 1; i < prices.size(); i++)
        {
            if (prices[i] - prices[i - 1] < 0)
            {
                ret += prices[i - 1] - prices[buy];
                buy = i;
            }
        }

        return ret + prices[prices.size() - 1] - prices[buy];
    }
};


class Solution
{
public:
    int largestSumAfterKNegations(vector<int>& nums, int k)
    {
        int ret = 0;
        priority_queue<int, vector<int>, greater<int>> heap;
        for (auto num : nums)
        {
            heap.push(num);
            ret += num;
        }

        while (k--)
        {
            int top = heap.top();
            heap.pop();

            heap.push(-top);
            ret -= 2 * top;
        }

        return ret;
    }
};

class Solution
{
public:
    vector<string> sortPeople(vector<string>& names, vector<int>& heights)
    {
        vector<int> index(names.size());
        for (int i = 0; i < index.size(); i++)
            index[i] = i;

        auto comp = [&](int a, int b) {
            return heights[a] > heights[b];
        };

        sort(index.begin(), index.end(), comp);

        vector<string> ret(names.size());
        for (int i = 0; i < names.size(); i++)
            ret[i] = names[index[i]];

        return ret;
    }
};

class Solution
{
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2)
    {
        vector<int> index1(nums1.size());
        vector<int> index2(nums2.size());
        for (int i = 0; i < index1.size(); i++)
            index1[i] = index2[i] = i;

        auto comp1 = [&](const int a, const int b) {
            return nums1[a] < nums1[b]; };

        auto comp2 = [&](const int a, const int b) {
            return nums2[a] < nums2[b]; };

        sort(index1.begin(), index1.end(), comp1);
        sort(index2.begin(), index2.end(), comp2);

        vector<int> ret(nums1.size());
        int j = 0;
        int tail = nums2.size() - 1;

        for (int i = 0; i < nums1.size(); i++)
        {
            if (nums1[index1[i]] > nums2[index2[j]])
                ret[index2[j++]] = nums1[index1[i]];
            else
                ret[index2[tail--]] = nums1[index1[i]];
        }

        return ret;
    }
};

class Solution
{
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2)
    {
        vector<int> index2(nums2.size());
        for (int i = 0; i < index2.size(); i++)
            index2[i] = i;

        sort(nums1.begin(), nums1.end());
        sort(index2.begin(), index2.end(),
            [&](const int a, const int b) {
                return nums2[a] < nums2[b]; });

        vector<int> ret(nums1.size());
        int j = 0;
        int tail = nums2.size() - 1;

        for (int i = 0; i < nums1.size(); i++)
        {
            if (nums1[i] > nums2[index2[j]])
                ret[index2[j++]] = nums1[i];
            else
                ret[index2[tail--]] = nums1[i];
        }

        return ret;
    }
};

class Solution
{
public:
    int longestPalindrome(string s)
    {
        vector<int> hash('z' - 'A' + 1, 0);

        for (auto ch : s)
            hash[ch - 'A']++;

        int ret = 0;
        bool flag = false;

        for (auto num : hash)
        {
            ret += (num / 2) * 2;

            if (num % 2 == 1)
                flag = true;
        }

        return flag ? ret + 1 : ret;
    }
};

class Solution
{
public:
    vector<int> diStringMatch(string s)
    {
        vector<int> ret(s.size() + 1);
        int left = 0, right = s.size();

        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == 'I')
                ret[i] = left++;
            else
                ret[i] = right--;
        }

        ret[s.size()] = left;
        return ret;
    }
};

class Solution
{
public:
    int findContentChildren(vector<int>& g, vector<int>& s)
    {
        int ret = 0;
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());

        for (int i = 0; i < s.size(); i++)
        {
            if (ret < g.size() && s[i] > g[ret])
                ret++;
        }

        return ret;
    }
};

class Solution
{
public:
    string optimalDivision(vector<int>& nums)
    {
        string ret = to_string(nums[0]);
        if (nums.size() == 1)
            return ret;
        else if (nums.size() == 2)
            return ret + "/" + to_string(nums[1]);
        else
            ret += "/(" + to_string(nums[1]);

        for (int i = 2; i < nums.size(); i++)
            ret += "/" + to_string(nums[i]);

        return ret + ")";
    }
};

class Solution
{
public:
    int jump(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> dp(n, INT_MAX); //   Ծ   i     С    
        dp[0] = 0;

        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (j + nums[j] >= i)
                    dp[i] = min(dp[i], dp[j] + 1);
            }
        }

        return dp[n - 1];
    }
};

class Solution
{
public:
    int jump(vector<int>& nums)
    {
        int n = nums.size();
        int ret = 0;
        int left = 0, right = 0;

        while (right < n - 1)
        {
            ret++;
            int newRight = right + 1;
            for (int i = left; i <= right; i++)
                newRight = max(newRight, i + nums[i]);

            left = right + 1;
            right = newRight;
        }

        return ret;
    }
};

class Solution
{
public:
    bool canJump(vector<int>& nums)
    {
        int n = nums.size();
        int left = 0, right = 0;

        while (right < n - 1)
        {
            int newRight = right + nums[right];

            for (int i = left; i <= right; i++)
                newRight = max(newRight, i + nums[i]);

            if (newRight == right)
                return false;

            left = right + 1;
            right = newRight;
        }

        return true;
    }
};

class Solution
{
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost)
    {
        int n = gas.size();

        for (int i = 0; i < n; i++)
        {
            int rest = 0;
            int step;
            for (step = 0; step < n; step++)
            {
                rest += gas[(i + step) % n] - cost[(i + step) % n];
                if (rest < 0) break;
            }

            if (rest >= 0) return i;
            i += step;
        }

        return -1;
    }
};